/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
export var multiply = function (num1, num2) {
  if (num1 === '0' || num2 === '0') return '0'
  const [len1, len2] = [num1.length, num2.length]
  const [numArr1, numArr2] = [num1.split('').reverse(), num2.split('').reverse()]
  let ans = ''
  for (let i = 0; i < len1; i++) {
    let carry = 0
    let curr = new Array(i).fill(0)
    for (let j = 0; j < len2; j++) {
      const n1 = numArr1[i]
      const n2 = numArr2[j]
      const sum = n1 * n2 + carry
      carry = Math.floor(sum / 10)
      curr.push(sum % 10)
    }
    if (carry > 0) {
      curr.push(carry)
    }
    ans = plus(ans, curr.reverse().join(''))
  }
  return ans
}

function plus(num1, num2) {
  if (num1.length < num2.length) return plus(num2, num1)
  num2 = num2.padStart(num1.length, '0')
  const len = num1.length
  const ans = new Array(len).fill(0)
  let [curr, carry] = [len - 1, 0]
  while (curr >= 0) {
    const [n1, n2] = [Number(num1[curr]), Number(num2[curr])]
    const sum = n1 + n2 + carry
    if (sum > 9) {
      carry = 1
      ans[curr] = sum - 10
    } else {
      carry = 0
      ans[curr] = sum
    }
    curr--
  }
  if (carry > 0) {
    ans.unshift(carry)
  }
  return ans.join('')
}

export function multiply2(num1, num2) {
  if (num1 === '0' || num2 === '0') return '0'
  const n = num1.length
  const m = num2.length
  // 申请n+m个位置，因为两位数相乘，乘积最大为n+m位，10 * 10 = 100； 9 * 9= 81
  const arr = new Array(n + m).fill(0)
  // 将乘积归纳为一个数组
  for (let i = n - 1; i >= 0; i--) {
    for (let j = m - 1; j >= 0; j--) {
      let num = +num1[i] * +num2[j]
      arr[i + j + 1] += num
    }
  }
  // 进位
  for (let i = n + m - 1; i > 0; i--) {
    arr[i - 1] += Math.floor(arr[i] / 10)
    arr[i] = arr[i] % 10
  }
  if (!arr[0]) {
    arr.splice(0, 1)
  }
  return arr.join('')
}
